let deux_a_deux_differentes liste =
  let rec examiner tete queue =
    match queue with
    | [] -> true
    | hd :: tl when not (tete = hd) -> examiner tete tl
    | _ -> false
  in
  let rec aux = function
    | [] -> true
    | hd :: tl when examiner hd tl ->
       aux tl
    | _ -> false
  in
  aux liste

let difference l1 l2 =
  let rec present x = function
    | [] -> false
    | hd :: _ when hd = x -> true
    | _ :: tl -> present x tl
  in
  let rec aux = function
    | [] -> []
    | hd :: tl when not (present hd l2) ->
       hd :: (aux tl)
    | _ :: tl ->
       aux tl
  in
  aux l1

let empty = function | [] -> true | _ -> false

module type TCarte =
  sig
    type carte
    val est_atout: carte -> bool
    val est_roi: carte -> bool
    val est_bout: carte -> bool
  end

module Make (Carte: TCarte) =
  struct
    type structure = 
      | Parmi of (int * (Carte.carte list))
      | ToutesEt of (Carte.carte list) * structure
    let structure_ecart =
      (* Sépare les cartes appelables tout le temps et les atouts*)
      let rec aux main = 
	match main with
	| [] -> ([], [])
	| c :: tl 
	     when not (Carte.est_atout c)
		  && not (Carte.est_bout c)
		  && not (Carte.est_roi c) -> 
	   let (normales, atouts) = aux tl in
	   (c :: normales, atouts)
	| c :: tl 
	     when not (Carte.est_bout c)
		  && not (Carte.est_roi c) -> 
	   let (normales, atouts) = aux tl in
	   (normales, c :: atouts)
	| _ :: tl -> aux tl
      in
      (* Dans les cas où il n'y a pas assez de cartes normales, *)
      (* pose les contraintes *)
      let obliger (normales, atouts) =
	match normales with
	| [] -> Parmi (3, atouts)
	| [ _ ] -> ToutesEt (normales, Parmi (2, atouts))
	| [ _ ; _ ] -> ToutesEt (normales, Parmi (1, atouts))
	| _ -> Parmi (3, normales)
      in
      fun cartes -> obliger (aux cartes)
    let rec respecte_structure ecart structure = 
      deux_a_deux_differentes ecart 
      &&
	match structure with
	| Parmi (n, liste) ->
	   let restantes = difference ecart liste in
	   (* restantes dans l'écart une fois enlevées les cartes possibles *)
	   List.length ecart = n && empty restantes
	| ToutesEt (oblig, s) ->
	   match difference oblig ecart with
	   | [] -> respecte_structure (difference ecart oblig) s
	   | _ -> false       
		    
  end
